# source:https://leetcode.cn/submissions/detail/601921950/ 模拟 hashtable
from collections import defaultdict


class Solution:
    def similarPairs(self, words: List[str]) -> int:
        store = []
        d = defaultdict(int)
        ans = 0
        for v in words:
            if store:
                for i, s in enumerate(store):
                    if set(v) == s:
                        ans += d[i]
                        d[i] += 1
                        break
                else:
                    store.append(set(v))
                    d[len(store)-1] += 1
            else:
                store.append(set(v))
                d[len(store)-1] += 1
        return ans

# source：https://leetcode.cn/problems/palindrome-partitioning-iv/ 划分DP 记忆化搜索 回文串预处理
from functools import cache
class Solution:
    def checkPartitioning(self, s: str) -> bool:

        @cache
        def dfs(i, cnt):
            if cnt == 0:
                if i < 0:
                    return True
                return False
            if i < 0:
                return False
            res = False
            for j in range(i+1):
                if is_palindrome[j][i]:
                    res |= dfs(j-1, cnt-1)
            return res

        n = len(s)
        
        # 预计算 is_palindrome[i][j]
        is_palindrome = [[False] * n for _ in range(n)]
        for length in range(n):
            for i in range(n - length):
                j = i + length
                if s[i] == s[j]:
                    if j - i <= 1:  # 长度 1 或 2 的字符串
                        is_palindrome[i][j] = True
                    else:
                        is_palindrome[i][j] = is_palindrome[i + 1][j - 1]

        return dfs(n-1, 3)

# source:https://leetcode.cn/problems/last-stone-weight-ii/ 0/1背包问题 DP
class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        total = sum(stones)
        n, m = len(stones), total // 2
        dp = [[False] * (m + 1) for _ in range(n + 1)]
        dp[0][0] = True

        for i in range(n):
            for j in range(m + 1):
                if j < stones[i]:
                    dp[i + 1][j] = dp[i][j]
                else:
                    dp[i + 1][j] = dp[i][j] or dp[i][j - stones[i]]
        
        ans = None
        for j in range(m, -1, -1):
            if dp[n][j]:
                ans = total - 2 * j  # total - j - j
                break
        
        return ans